﻿// 0928train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
为了提升软件编码能力，小王制定了刷题计划，他选了题库中的n道题，4
编号从0到n-1，并计划在m天内按照题目编号顺序刷完所有的题目（注意，小王不能用多天完成同一题）
在小王刷题计划中，小王需要用time[i]的时间完成编号的题目此外，
小王还可以查看答案，可以省去该题的做题时间
小王每天最多直接看一次答案。我们定义m天中做题时间最多的一天耗时为T
（直接看答案的题目不计入做题总时间）。请你帮小王求出最小的T是多少

输入描述
第一行输入为 time，time[i]的时间完成编号的题目
第二行输入为m，m表示几天内完成所有题目，1 <= m <= 180
输出描述
最小耗时整数T

示例1：
输入
999,999,999
4
输出
0
说明
在前三天中，小王每天都直接看答案，这样他可以在三天内完成所有的题目并不花任何时间

示例2：
输入
1,2,2,3,5,4,6,7,8
5
输出
4
说明
第一天完成前3题，第3题看答案第二天完成第4题和第5题，第5题看答案:第三天完成第6和第7题，第7题看答案:第四天完成第8题，直接看答案:第五天完成第9题，直接看答案
 */
class Solution01
{
public:
    bool checkVerify(int sum_limit, vector<int>& num_vec, int len_limit)
    {
        //可以去掉这一段最大的
        int curr_len = 1;
        vector<int>track_v = { num_vec[0] };
        int v_size = num_vec.size();
        for (int i = 1; i < v_size; i++)
        {
            track_v.push_back(num_vec[i]);
            long long curr_sum = accumulate(track_v.begin(), track_v.end(), 0LL);
            int max_num = *max_element(track_v.begin(), track_v.end());
            curr_sum -= max_num;
            if (curr_sum > sum_limit)
            {
                curr_len++;
                track_v = { num_vec[i] };
            }
            //for---
        }
        return curr_len <= len_limit;

	    //checkVerify
    }

    Solution01(vector<int>&num_vec, int len_limit)
    {
        int sum = accumulate(num_vec.begin(), num_vec.end(), 0LL);
        int left = 0, right = sum+1;
        int v_size = num_vec.size();

        if (v_size<=len_limit)
        {
	        //每天都免除最大，每天都不用花时间
            cout << 0;
            return;
        }

        int result = 0;
        while (left<right)
        {
            int mid = left + (right - left) / 2;
            if (checkVerify(mid, num_vec,len_limit))
            {
                //合格，减少做题速度
                result = mid;
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        cout << result;

	    //Solution01
    }
};


class Solution02 {
public:
    bool checkVerify(long long sum_limit, vector<int>& time, int m)
    {
        int curr_len = 1;
        vector<int>track_v = { time[0] };
        int v_size = time.size();
        for (int i=1; i< v_size; i++)
        {
            track_v.push_back(time[i]);
            long long curr_sum = accumulate(track_v.begin(), track_v.end(), 0LL);
            int max_num = *max_element(track_v.begin(), track_v.end());
            curr_sum -= max_num;
            if (curr_sum>sum_limit)
            {
                curr_len++;
                track_v = { time[i] };
            }
	        //for---
        }
        return curr_len <= m;
    }

    int minTime(vector<int>& time, int m) {
        if (time.size() <= m)
        {
            return 0;
        }

        long long result = 0;
        long long sum = accumulate(time.begin(), time.end(), 0LL);
        long long left = 0, right = sum + 1;
        while (left < right)
        {
            long long mid = left + (right - left) / 2;
            if (checkVerify(mid, time, m))
            {
                //达标，缩小每日耗时
                result = mid;
                right = mid;
            }
            else
            {
                left = mid + 1;
            }

        }

        return result;
    }
};


/*
 小明是核心网工程师，客户交给小明一个任务：
 给定一个网络配置列表，每个配置是一个字符串，仅由数字和“*”、“?”符号组成
 输入用户的IMSI（国际移动用户识别码），根据以下规则匹配配置列表：
“*”匹配0个或连续多个任意字符，
“?”匹配下标为奇数的单个字符，比如123?中的“?”可以匹配1234567890123456下标为3的字符‘4’，
下标从0开始。

输入描述
输入第一行为网络配置列表，列表中的每个配置是由数字和“*”、“?”组成的字符串
每个字符串中“*”不会超过一个，“?”若干，网络配置列表长度小于200，每个字符串以英文逗号隔开
输入第二行为用户的IMSI（国际移动用户识别码），仅由数字组成，长度等于15
备注
保证输入格式正确，无需考虑格式错误。

输出描述
输出为满足匹配规则的配置字符串列表，列表按字典序升序输出，每个字符以英文逗号隔开
若没有满足条件的配置，则返回字符串“null”
示例1
输入：
1234567,1234567*
123456789012345
输出：
1234567*
说明：
*可以匹配0或多个任意字符，故输出1234567*

示例2
输入：
123????????7345,123????*????3345
123456789012345
输出：
null
说明：
“?”字符只能匹配IMSI中为奇数下标的字符，故都不符合要求，返回null

11*?2
11002
 */
class Solution03
{
public:
    bool checkVerify(string&role_str, string&verify_str)
    {
        int role_size = role_str.size();
        int verify_size = verify_str.size();

        int role_i = 0;
        int verify_i= 0;
        bool all_res = true;
        while (role_i< role_size && verify_i< verify_size)
        {
            if (role_str[role_i]=='*')
            {
                if (role_i== role_size -1)
                {
                    return true;
                }
                
                all_res = false;
                role_i++;
                //在verify_str里找到匹配下一个role_i的字符
                //下一个role_i要么是?，要么是字符
                char role_ch = role_str[role_i];
                if (role_ch=='?')
                {
                    while (verify_i < verify_size && verify_i % 2 == 0)
                    {
                        verify_i++;
                    }
                    if (verify_i < verify_size && verify_i % 2 == 1)
                    {
                        all_res = true;
                        role_i++;
                        verify_i++;
                    }

                }
                else
                {
                    while (verify_i < verify_size && role_str[role_i] != verify_str[verify_i])
                    {
                        verify_i++;
                    }
                    if (verify_i < verify_size && role_str[role_i]==verify_str[verify_i])
                    {
                        all_res = true;
                        role_i++;
                        verify_i++;
                    }
                }

                continue;
            }
            if (role_str[role_i] == '?')
            {
                //?匹配奇数下标
                if (verify_i % 2 == 0) return false;

                role_i++; verify_i++;
                continue;
            }
            if (role_str[role_i]!=verify_str[verify_i])
            {
                return false;
            }
            //相等继续比较
        	role_i++; verify_i++;
            //while--
        }

        if (!all_res) return false;
        return verify_i == verify_size && role_i == role_size;
	    //checkVerify
    }

    Solution03(vector<string>&role_vec, string&verify_str)
    {
        //输出为满足匹配规则的配置字符串列表，列表按字典序升序输出
        vector<string>result;
        for (auto&role_str:role_vec)
        {
            if (checkVerify(role_str, verify_str))
            {
                result.push_back(role_str);
            }
	        //for---
        }

        if (result.empty())
        {
            cout << "null";
            return;
        }


        sort(result.begin(), result.end(), [](string&str_1, string&str_2)
            {
                return str_1 < str_2;
            });
        int result_size = result.size();
        for (int i=0; i<result_size; i++)
        {
            cout << result[i];
            if (i!=result_size-1)
            {
                cout << ',';
            }
        }

	    //Solution03
    }
};

class Solution13
{
public:
    bool checkVerify(string& role_str, string& verify_str)
    {
        if (role_str.find('*')==string::npos && role_str.find('?')==string::npos)
        {
            return role_str == verify_str;
        }

        if (role_str == "*") return true;

        int role_size = role_str.size(), verify_size = verify_str.size();
        int row_size = role_size + 1, col_size = verify_size + 1;

        vector<vector<bool>>dynamic_v(row_size,vector<bool>(col_size,false));

        //空串匹配空串
        dynamic_v[0][0] = true;
        if (role_str[0] == '*')
        {
            dynamic_v[1][0] = true;
        }

        for (int r=1; r<row_size; r++)
        {
            char role_ch = role_str[r-1];
            for (int c=1; c<col_size; c++)
            {
                if (role_ch=='*')
                {
                    dynamic_v[r][c] = dynamic_v[r - 1][c] || dynamic_v[r][c - 1];
                }
                else if (role_ch=='?')
                {
                    if ((c - 1) % 2 == 1) dynamic_v[r][c] = dynamic_v[r - 1][c - 1];

                }
                else
                {
                    if (role_str[r-1]==verify_str[c-1])
                        dynamic_v[r][c] = dynamic_v[r - 1][c - 1];
                }
                //for---
            }
            //for--
        }
        //role_size verify_size
        return dynamic_v[role_size][verify_size];
        //checkVerify
    }
    Solution13(vector<string>& role_vec, string&verify_str)
    {
        //输出为满足匹配规则的配置字符串列表，列表按字典序升序输出
        vector<string>result;
        for (auto& role_str : role_vec)
        {
            if (checkVerify(role_str, verify_str))
            {
                result.push_back(role_str);
            }
            //for---
        }

        if (result.empty())
        {
            cout << "null";
            return;
        }


        sort(result.begin(), result.end(), [](string& str_1, string& str_2)
            {
                return str_1 < str_2;
            });
        int result_size = result.size();
        for (int i = 0; i < result_size; i++)
        {
            cout << result[i];
            if (i != result_size - 1)
            {
                cout << ',';
            }
        }

	    //Solution13
    }
};


/*
代号为 x 的国家和代号为 y 的国家分别需要 cntx 名和 cnty 名员工
部门每个员工有一个员工号 (1,2,3,......)，工号连续，从 1 开始
部长派遣员工的规则：
规则1：从 1,k 中选择员工派遣出去
规则2：编号为 x 的倍数的员工不能去 x 国，编号为 y 的倍数的员工不能去 y 国
问题
找到最小的 k，使得可以将编号在 [1,k] 中的员工分配给 x 国和 y 国，且满足 x 国和 y 国的需求

输入描述
四个整数 x,y,cntx,cnty
2 < x < y < 30000
x和y 一定是 质数
1 < cntx, cnty < 10^9
cntx + cnty < 10^9

输出描述
满足条件的最小的 k
示例1：
输入：
2 3 3 1
输出：
5
说明：
输入中：
2 表示国家代号 2
3 表示国家代号 3
3 表示国家 2 需要3个人
1 表示国家 3 需要1个人
输出的5表示k最小为5
 */
class Solution04
{
public:
    bool checkVerify(int k, int x, int y, int cntx, int cnty)
    {
        //k里不能去x，但能去y的人
        int goto_y = k / x - k / (x * y);
        //k里不能去y，但能去x的人
        int goto_x = k / y - k / (x * y);

        int need_free_x = max(0, cntx - goto_x);
        int need_free_y = max(0, cnty - goto_y);

        //既能去x又能去y的人
        int free = k - k / x - k / y + k / (x * y);

        return free >= need_free_x + need_free_y;
	    //checkVerify
    }

    Solution04(int x, int y, int cntx, int cnty)
    {
        //x,y,cntx,cnty
        int result = 0;
        int left = 0, right = INT_MAX;
        while (left<right)
        {
            int mid = left+(right - left) / 2;

            if (checkVerify(mid, x,y,cntx,cnty))
            {
                //满足条件，缩小mid
                result = mid;
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
	        //while---
        }
        cout << result;

	    //Solution04
    }
};


int main()
{
	{
        //x,y,cntx,cnty
        //2 3 3 1
        int x, y, cntx, cnty;
        cin >> x >> y >> cntx >> cnty;

        Solution04 solu(x, y, cntx, cnty);

        return 0;
	}
	{
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<string>str_vec;
        while (getline(oh_sstream,token, ','))
        {
            str_vec.push_back(token);
	        //while---
        }
        string verify_str;
        getline(cin, verify_str);
        Solution13 solu(str_vec, verify_str);


        return 0;
	}
	{
        vector<int>num_vec = { 1,2,3,3 };
        int m = 2;
        Solution02 solu;
        cout << solu.minTime(num_vec, m);

        return 0;
	}
    //1,2,2,3,5,4,6,7,8
    //5
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    vector<int>num_vec;
    while (getline(oh_sstream,token,','))
    {
        num_vec.push_back(stoi(token));
    }
    string len_str;
    getline(cin, len_str);
    int len_limit = stoi(len_str);

    Solution01 solu(num_vec, len_limit);


    //main---
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
